package main

import "fmt"

func main() {
	nums := []int{3, 2, 1, 6, 9, 0}
	bubbleSort(nums)
	fmt.Print(nums)
}

// func bubbleSort(nums []int) {
// 	for i := 0; i < len(nums)-1; i++ {
// 		doSwap := false
// 		for j := 0; j < len(nums)-i-1; j++ { // 最后 i 个已经是有序的最大元素，不用再动
// 			if nums[j] > nums[j+1] {
// 				nums[j], nums[j+1] = nums[j+1], nums[j]
// 				doSwap = true
// 			}
// 		}
// 		if !doSwap {
// 			break
// 		}
// 	}
// }

// 冒泡排序
func bubbleSort(nums []int) {
	for i := 0; i < len(nums)-1; i++ {
		doswap := false
		for j := 0; j < len(nums)-1-i; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
				doswap = true
			}
		}
		if !doswap {
			break
		}
	}
}

// 快速排序
func quickSort(nums []int, lo, hi int) {
	if lo >= hi {
		return
	}

	p := partition(nums, lo, hi)
	quickSort(nums, lo, p-1)
	quickSort(nums, p+1, hi)
}

func partition(nums []int, lo, hi int) int {
}

// 堆排序
